Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
до курсової роботи (Частина 2)
з дисципліни: “ Програмування. Частина III. Структури даних та алгоритми ”
на тему: “ ”
Процес знаходження номеру варіанта індивідуального завдання
Вибір АТД:
№ = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 3 + 1 = [(21) + (7) + (66) ] % 3 + 1 = 2
Примітка: 1 – стек, 2 – черга, 3- список.
Вибір номера завдання:
№ = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 10 + 1 =
= [(21) + (66) ] % 10 + 1 = 8
Зміст
1. Теоретична частина. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3ст.
2. Частина 1. Побудова АТД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 1. Постановка задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 2. Динаміка вмісту. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 3. Результати виконання програми. . . . . . . . . . . . . . . . . . . . . . 6ст.
3. Частина 2. Застосування АТД. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.1. Постановка задачі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.2. Алгоритм розв’язання задачі. . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.3. Результати виконання програми. . . . . . . . . . . . . . . . . . . . . . . 8ст.
Висновки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9ст.
Список літератури. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10ст.
Додатки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11ст.
1.Теоретична частина
СТЕК
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку.
Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті.
ЧЕРГА
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує...